package lc.排序算法;

import java.util.Arrays;

/**
 * @description:
 * @author: qian
 * @createDate: 2021/11/9
 */
public class menger {


    /**
     * 时间复杂度O(nlogn) 空间复杂度0(n) 稳定
     * @param arr
     * @param l
     * @param r
     */
    public void mergeSort(int[] arr, int l, int r) {
        int[] tmp = new int[r + 1];
        if (l >= r) return;

        int mid =l + r >> 1;

        mergeSort(arr,l,mid);
        mergeSort(arr,mid + 1,r);

        int k = 0, i = l, j = mid + 1;
        while (i <= mid && j <= r) {
            if (arr[i] <= arr[j]) tmp[k++] = arr[i++];
            else tmp[k++] = arr[j++];
        }
        while (i <= mid) tmp[k++] = arr[i++];
        while (j <= r) tmp[k++] = arr[j++];

        for (i = l, j = 0; i <= r; i++, j++) {
            arr[i] = tmp[j];
        }

    }
    public static void main(String[] args) {

        menger q = new menger();

        int[] a = {1,45,73,7,3676,7,234,2,34,78,54,24};
        q.mergeSort(a,0,a.length - 1);
        System.out.println(Arrays.toString(a));
    }
}
